package simplex;

import java.io.*;
import java.util.ArrayList;

public class Simplex {
    public static void main(String[] args) {
        // 定义矩阵和向量
        ArrayList<ArrayList<Double>> A = new ArrayList<>();
        ArrayList<Double> b = new ArrayList<Double>();
        ArrayList<Double> c = new ArrayList<Double>();

        // 读入文件
        String filePath = "src/simplex/sample.txt";
        try {
            FileReader fr = new FileReader(filePath);
            BufferedReader br = new BufferedReader(fr);
            String line;
            String[] temp;
            int i = 0;
            while ((line = br.readLine()) != null) {

                temp = line.split(" ");
                if (i == 0) {
                    // 填充c
                    for (int j = 0; j < temp.length - 1; j++) {
                        c.add(Double.valueOf(temp[j]));
                    }
                } else {
                    // 填充A和b
                    ArrayList<Double> tempList = new ArrayList<Double>();
                    for (int j = 0; j < temp.length; j++) {
                        tempList.add(Double.valueOf(temp[j]));
                        if (j == temp.length - 1) {
                            b.add(Double.valueOf(temp[j]));
                        }
                    }
                    A.add(tempList);
                }
                i++;

            }
            br.close();
        } catch (IOException e) {
        }
        // 实例化求解对象
        Solver solver = new Solver(A, b, c);
        solver.showModel();
        solver.solve();
    }
}

class Solver {

    ArrayList<ArrayList<Double>> A = new ArrayList<>();
    ArrayList<Double> b = new ArrayList<Double>();
    ArrayList<Double> c = new ArrayList<Double>();

    private ArrayList<Integer> x_b = new ArrayList<Integer>(); // 基变量

    private final int c_length;
    private final int b_length;

    Solver(ArrayList<ArrayList<Double>> A, ArrayList<Double> b, ArrayList<Double> c) {
        this.A = A;
        this.b = b;
        this.c = c;
        c_length = c.size();
        b_length = b.size();
    }

    void showModel() {
        // 输出目标函数
        String obj = "Max z = ";
        for (int i = 0; i < c_length; i++) {
            obj += c.get(i).toString() + "x" + Integer.toString(i);
            if (i != c_length - 1) {
                obj += " + ";
            }
        }
        System.out.println(obj);
        System.out.println("Subject to:");

        // 输出约束
        for (int i = 0; i < b_length; i++) {
            String con = "";
            for (int j = 0; j < c_length; j++) {
                // System.out.println(c.size());
                con += Double.toString(A.get(i).get(j)) + "x" + Integer.toString(j);
                if (j != c_length - 1) {
                    con += " + ";
                }
            }
            con += " = " + Double.toString(b.get(i));
            System.out.println(con);
        }
    }

    // 计算检验数和theta，选择换入换出变量
    private boolean pivot() {
        double cmax = -Double.MAX_VALUE; // 每一次迭代中最大的检验数
        double theta = Double.MAX_VALUE; // 每一次迭代中最小的theta
        int xout = 0; // 出基变量
        int xin = 0; // 进基变量
        // 计算检验数，并取出最大的一个
        for (int i = 0; i < c_length; i++) {
            double temp = c.get(i);
            for (int j = 0; j < b_length; j++) {
                temp -= c.get(x_b.get(j)) * A.get(j).get(i);
            }
            if (cmax < temp) {
                cmax = temp;
                xin = i;
            }
        }
        // 如果最大的检验数小于等于0,则已得到最优解
        if (cmax <= 0) {
            return true;
        }
        // 计算theta，并选出最小的一个
        for (int i = 0; i < b_length; i++) {
            double temp = A.get(i).get(c_length) / A.get(i).get(xin);
            if (theta > temp) {
                theta = temp;
                xout = x_b.get(i);
            }
        }
        // 更新基变量
        x_b.set(x_b.indexOf(xout), xin);
        // 高斯行变换
        gaussian(x_b.indexOf(xin), xin);
        return false;
    }

    // 高斯行变换：将主元变为1，然后将主元所在的列中其他元素变为0
    private void gaussian(int row, int column) {
        double p = A.get(row).get(column);
        for (int i = 0; i < c_length + 1; i++) { // 这里+1表示将b列一同纳入变换的范畴，下同
            A.get(row).set(i, A.get(row).get(i) / p);
        }

        for (int i = 0; i < b_length; i++) {
            if (i == row) {
                continue;
            }

            double a = A.get(i).get(column);
            for (int j = 0; j < c_length + 1; j++) {
                A.get(i).set(j, A.get(i).get(j) - a * A.get(row).get(j));
            }
        }
    }

    public void solve() {
        // 初始基变量默认为最后b_length个变量
        for (int i = 0; i < b_length; i++) {
            x_b.add(c_length + i - b_length);
        }

        while (true) {
            System.out.println(A.toString());
            double z = 0;
            for (int i = 0; i < b_length; i++) {
                z += c.get(x_b.get(i)) * A.get(i).get(c_length);
            }
            System.out.println("Z = " + z);
            if (pivot()) {
                System.out.println("最优解为：");
                for (int i = 0; i < c_length; i++) {
                    System.out.println("x" + Integer.toString(i) + " = "
                            + (x_b.indexOf(i) != -1 ? Double.toString(A.get(x_b.indexOf(i)).get(c_length)) : "0"));
                }
                break;
            }
            System.out.println("================================================");
        }
    }
}